import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

/**
 * Created by zhourh on 2018/8/7.
 *
 * 给定一个N叉树，返回其节点值的前序遍历。
 *
 */
public class NAryTreePreorderTraversal {

    public static void main(String[] args) {
        Node root = new Node();
        root.val = 1;
        Node node2 = new Node();
        node2.val = 2;
        Node node3 = new Node();
        node3.val = 3;
        Node node4 = new Node();
        node4.val = 4;
        Node node5 = new Node();
        node5.val = 5;
        Node node6 = new Node();
        node6.val = 6;
        List<Node> level2 = new ArrayList<>();
        level2.add(node3);
        level2.add(node2);
        level2.add(node4);
        root.children = level2;
        List<Node> level3 = new ArrayList<>();
        level3.add(node5);
        level3.add(node6);
        node3.children = level3;

        System.out.println(new NAryTreePreorderTraversal().preorder(root));
    }

    public List<Integer> preorder(Node root) {
        List<Integer> ans = new ArrayList<>();
        if (root == null) {
            return ans;
        }

        Stack<Node> stack = new Stack<>();
        stack.push(root);

        while (!stack.isEmpty()) {
            Node node = stack.pop();
            ans.add(node.val);

            if (node.children != null && !node.children.isEmpty()) {
                for (int i = node.children.size() - 1; i >= 0; i--) {
                    stack.push(node.children.get(i));
                }
            }
        }

        return ans;
    }
}
